package LC;

import java.util.ArrayList;

/**
 * https://leetcode.com/problems/median-of-two-sorted-arrays/description/
 * There are two sorted arrays nums1 and nums2 of size m and n respectively.
 * Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
 * Example 1:
 * nums1 = [1, 3]
 * nums2 = [2]
 * The median is 2.0
 * Example 2:
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * The median is (2 + 3)/2 = 2.5
 */
public class LC_004_MedianOfTwoSortedArrays_TwoPointers_Recur_BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 6};
        int[] b = {3, 4, 8, 9};
        double medianSortedArrays = Solution_2.findMedianSortedArrays(a, b);
        System.out.println(medianSortedArrays);
    }

    static class Solution_1 {
        private static double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int i = 0, j = 0;
            ArrayList<Integer> arr = new ArrayList<>();
            while (i < nums1.length && j < nums2.length) {
                if (nums1[i] > nums2[j]) arr.add(nums2[j++]);
                else arr.add(nums1[i++]);
            }
            while (i < nums1.length) arr.add(nums1[i++]);
            while (j < nums2.length) arr.add(nums2[j++]);
            int n = arr.size();
            if (n % 2 == 0) return (arr.get(n / 2) + arr.get(n / 2 - 1)) / 2.0;
            else return arr.get(n / 2);
        }
    }

    static class Solution_2 {
        private static double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int totalLen = nums1.length + nums2.length;
            if (totalLen % 2 == 0)
                return (findKth(totalLen / 2 + 1, nums1, nums2, 0, 0) + findKth(totalLen / 2, nums1, nums2, 0, 0)) / 2.0;
            return findKth(totalLen / 2 + 1, nums1, nums2, 0, 0);
        }

        private static int findKth(int k, int[] nums1, int[] nums2, int idx1, int idx2) {
            //当指针指向最后一个时候，就是另一个数组第k-1个
            if (idx1 >= nums1.length)
                return nums2[idx2 + k - 1];
            if (idx2 >= nums2.length)
                return nums1[idx1 + k - 1];
            //归并后的第一个
            if (k == 1)
                return Math.min(nums1[idx1], nums2[idx2]);

            //二分查找
            int m1 = idx1 + k / 2 - 1;
            int m2 = idx2 + k / 2 - 1;

            int mid1 = (m1 < nums1.length) ? nums1[m1] : Integer.MAX_VALUE;
            int mid2 = (m2 < nums2.length) ? nums2[m2] : Integer.MAX_VALUE;

            if (mid1 < mid2)
                return findKth(k - k / 2, nums1, nums2, m1 + 1, idx2);
            return findKth(k - k / 2, nums1, nums2, idx1, m2 + 1);
        }
    }

}
